package com.kevin.Code.Hash;

import java.util.HashMap;

/**
 * @author Vinlee Xiao
 * @Classname LRUCache
 * @Description Leetcode 146 LRU缓存机制 中等等难度 高频
 * @Date 2021/11/6 10:56
 * @Version 1.0
 */
public class LRUCache {

    public class DoubleNode {
        //存储健
        private int key;
        private int value;
        //分别指向前驱结点、后驱结点
        DoubleNode pre, next;

        public DoubleNode() {
        }

        ;

        public DoubleNode(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }

    private int capacity;
    private int size;
    DoubleNode head, tail;
    HashMap<Integer, DoubleNode> map;

    public LRUCache(int capacity) {

        this.capacity = capacity;
        head = new DoubleNode();
        tail = new DoubleNode();
        map = new HashMap<>();
        head.next = tail;
        tail.pre = head;
    }

    /**
     * 得到某个结点
     * 1.不存在直接返回-1
     * 2.存在 则返回关键字
     *
     * @param key
     * @return
     */
    public int get(int key) {

        if (!map.containsKey(key)) {
            return -1;
        }
        //得到该结点，并将其移动到头部
        DoubleNode node = map.get(key);
        //移动结点到头部
        moveToHead(node);

        return node.value;

    }

    /**
     * @param key
     * @param value
     */
    public void put(int key, int value) {

        //1.如果关键字存在，则变更其数据
        if (map.containsKey(key)) {

            DoubleNode node = map.get(key);
            node.value = value;
            moveToHead(node);
            map.put(key, node);

        } else {

            if (size >= capacity) {

                DoubleNode removeNode = removeTailNode();
                int k = removeNode.key;
                map.remove(k);
                size--;
            }

            //2.加入到头结点中
            DoubleNode node = new DoubleNode(key, value);
            addToHead(node);
            //加入到hash表中
            map.put(key, node);
            //大小加1
            size++;

        }
    }

    /**
     * @return
     */
    public DoubleNode moveToHead(DoubleNode node) {

        //先删除node
        removeNode(node);
        addToHead(node);

        return node;
    }

    /**
     * 将结点移动到头结点
     *
     * @param node
     */
    public void addToHead(DoubleNode node) {

        head.next.pre = node;
        node.next = head.next;
        node.pre = head;
        head.next = node;
    }


    /**
     * 删除结点
     *
     * @param node
     * @return
     */
    public void removeNode(DoubleNode node) {

        node.next.pre = node.pre;
        node.pre.next = node.next;
    }


    /**
     * 删除最后一个结点
     */
    public DoubleNode removeTailNode() {
        DoubleNode node = tail.pre;
        removeNode(node);
        return node;
    }
}
